package com.sourcetrip.my;


import com.sourcetrip.my.abs.AbstractBinaryTree;
import com.sourcetrip.my.modle.TreeNode;

import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2020/12/15
 * @description: 二叉搜索树 设计：
 * 1.普通的二叉搜索树，具有元素比较的能力；通过 constructor 传入比较器。
 * 2.
 * --
 * 由于方法具有通用性，就木有版本V 一说了
 */
public class BinarySearchTree<E> extends AbstractBinaryTree<E> {
	private Comparator<E> comparator;

	//region	constructors

	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}

	public BinarySearchTree() {

	}
	//endregion

	/**
	 * 二叉搜索树添加元素
	 * 需要保留一个 prev 的引用指向父节点
	 * O(h-树的高度)
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		elementNotNullCheck(element);
		if (size == 0) {
			root = createNode(element, null);
			//new TreeNode<>(element, null);
			size++;
			//add 修复
			afterAdd(root);
			return;
		}

		TreeNode<E> cur = root;
		TreeNode<E> prev = null;
		while (cur != null) {
			int compare = compare(element, cur.element);
			//如果 相等，将元素进行替换
			if (compare == 0) {
				cur.element = element;
				return;
			}
			prev = cur;
			if (compare > 0) {
				cur = cur.right;
			} else {
				cur = cur.left;
			}
		}

		//此时找到了 prev 就是 所要添加节点的父节点
		TreeNode<E> node = createNode(element, prev);
		int compare = compare(element, prev.element);
		if (compare > 0) {
			prev.right = node;
		} else {
			prev.left = node;
		}
		size++;
		afterAdd(node);
	}


	/**
	 * 二叉搜索树的删除节点
	 * 有点复杂，需要讨论删除节点的度情况：
	 * 0,1,2
	 *
	 * @param element
	 */
	@Override
	public void remove(E element) {
		remove(root, element);
	}

	@Override
	public boolean contains(E element) {
		return false;
	}


	/**
	 * 查找前驱节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public TreeNode<E> predecessor(TreeNode<E> node) {
		if (node == null || node.left == null) {
			return null;
		}
		TreeNode<E> cur = node.left;
		while (cur.right != null) {
			cur = cur.right;
		}
		//此时 cur 即 前驱节点
		return cur;
	}

	/**
	 * 查找后继节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public TreeNode<E> successor(TreeNode<E> node) {
		if (node == null || node.right == null) {
			return null;
		}
		TreeNode<E> cur = node.right;
		while (cur.left != null) {
			cur = cur.left;
		}
		//此时 cur 即 后继节点
		return cur;
	}

	//region	private methods

	/**
	 * 比较两个元素
	 *
	 * @param e1
	 * @param e2
	 * @return
	 */
	private int compare(E e1, E e2) {
		int res = 0;
		try {
			res = (comparator != null) ? comparator.compare(e1, e2) : ((Comparable) e1).compareTo(e2);
		} catch (Exception e) {
			throw new RuntimeException("元素比较发生了异常！");
		} finally {
			return res;
		}
	}

	/**
	 * 从 node 开始，删除其中的 element
	 *
	 * @param node
	 * @param element
	 */
	private void remove(TreeNode<E> node, E element) {
		elementNotNullCheck(element);
		//根节点 为空，直接返回
		if (node == null) {
			return;
		}
		TreeNode<E> cur = node;
		while (cur != null) {
			int compare = compare(element, cur.element);
			if (compare == 0) {
				//找到删除的元素
				break;
			}
			if (compare > 0) {
				cur = cur.right;
			} else {
				cur = cur.left;
			}
		}
		if (cur == null) {
			//此时没有找到元素，直接返回
			return;
		}
		TreeNode<E> parent = cur.parent;
		//此时 cur == 要删除的元素
		if (cur.left == null && cur.right == null) {
			//如果是 叶子节点
			if (parent != null) {
				if (cur.isLeftChild()) {
					parent.left = null;
				} else {
					parent.right = null;
				}
			} else {
				//TODO:忽略了 根节点元素的处理
				root = null;
			}
			//删除之后的修复
			//afterRemove(cur);
			afterRemove(cur, null);
		} else if (cur.left != null && cur.right != null) {
			//如果是 度 == 2
			//1.找到 前驱/后继节点
			TreeNode<E> predecessor = predecessor(cur);
			//2.用 前驱/后继节点 的 ele 替换 cur
			cur.element = predecessor.element;
			//3.删除 前驱/后继节点
			remove(cur.left, cur.element);
			//此处没有真正的删除，不做修复
		} else if (cur.left != null) {
			//度 == 1 && 左节点不为空
			if (parent != null) {
				if (cur.isLeftChild()) {
					parent.left = cur.left;
				} else {
					parent.right = cur.left;
				}
			}
			//处理 node.left 的父节点
			cur.left.parent = parent;
			//删除之后的修复
			//afterRemove(cur);
			afterRemove(cur, cur.left);
		} else {
			//度 == 1 && 右节点不为空
			if (parent != null) {
				if (cur.isLeftChild()) {
					parent.left = cur.right;
				} else {
					parent.right = cur.right;
				}
			}
			cur.right.parent = parent;
			//删除之后的修复
			//afterRemove(cur);
			afterRemove(cur, cur.right);
		}
		size--;
	}

	/**
	 * 检查元素 是否为 null
	 *
	 * @param element
	 */
	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}

	//endregion

	//region	protected methods

	/**
	 * 创建节点
	 *
	 * @param element 添加的元素
	 * @param parent  添加的节点的父节点
	 * @return
	 */
	protected TreeNode<E> createNode(E element, TreeNode<E> parent) {
		return new TreeNode<>(element, parent);
	}

	/**
	 * 在 添加之后进行修复
	 *
	 * @param node 添加的节点
	 */
	protected void afterAdd(TreeNode<E> node) {

	}

	/**
	 * 在 移除元素 之后进行修复
	 *
	 * @param node
	 */
	protected void afterRemove(TreeNode<E> node) {

	}

	/**
	 * 删除之后的修复
	 *
	 * @param node        删除的节点
	 * @param replacement 替换的节点
	 */
	protected void afterRemove(TreeNode<E> node, TreeNode<E> replacement) {

	}

	/**
	 * 获取 node 节点的 叔叔节点
	 * node.parent.parent.another son
	 * 最开始用于红黑树中，但是可以在 BinaryTree 中通用
	 *
	 * @param node
	 * @return uncle node
	 */
	protected TreeNode<E> getUncleNode(TreeNode<E> node) {
		if (node == null) {
			return null;
		}
		TreeNode<E> parent = node.parent;
		if (parent == null) {
			return null;
		}
		TreeNode<E> grand = parent.parent;
		if (grand == null) {
			return null;
		}
		if (parent.isLeftChild()) {
			return grand.right;
		} else {
			return grand.left;
		}
	}

	/**
	 * 获取 node 的兄弟节点
	 * 用于红黑树中，但是其实可以通用于 二叉树
	 *
	 * @param node
	 * @return
	 */
	protected TreeNode<E> getSiblingNode(TreeNode<E> node) {
		if (node == null) {
			return null;
		}
		TreeNode<E> parent = node.parent;
		if (parent == null) {
			return null;
		}
		if (node.isLeftChild()){
			return parent.right;
		}else if (node.isRightChild()){
			return parent.left;
		}else {
			return null;
		}
	}

	//endregion

}
